package test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author sunzhuokun
 * @date 14:33 2024/5/14
 * @description 二叉树中序遍历
 * 根据给定的二叉树结构描述字符串，输出该二叉树按照中序遍历结果字符串。中序遍历顺序为:左子树，根结点，右子树。
 * <p>
 * 输入描述
 * 由大小写字母、左右大括号、逗号组成的字符串:
 * 1、字母代表一个节点值，左右括号内包含该节点的子节点。
 * 2、左右子节点使用逗号分隔，逗号前为空则表示左子节点为空,没有逗号则表示右子节点
 * 为空。
 * 3、二叉树节点数最大不超过100。
 * 注:输入字符串格式是正确的，无需考虑格式错误的情况。
 * <p>
 * 输出描述
 * 输出一个字符串，为二叉树中序遍历各节点值的拼接结果。
 * <p>
 * 示例：
 * 输入：a{b{d, e{g,h{,I}}},c{f}｝
 * 输出：dbgehiafc
 */
public class MiddleOrderTraversalOfBinaryTree_二叉树中序遍历 {
    static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }

    public static void main(String[] args) {
        // 以下算法有问题
        System.out.println(inorderTraversalFromString("a{b{d,e{g,h{,I}}},c{f}}"));
    }

    public static String inorderTraversalFromString(String input) {
        TreeNode root = buildTree(input, 0);
        return inorderTraversal(root);
    }

    private static String inorderTraversal(TreeNode node) {
        List<Character> result = new ArrayList<>();
        inorder(node, result);
//        System.out.println(result);
        return result.stream().map(String::valueOf).reduce((a, b) -> a + b).orElse("");
    }

    private static void inorder(TreeNode node, List<Character> result) {
        if (node == null) {
            return;
        }
        inorder(node.left, result);
        result.add((char) node.val);
        inorder(node.right, result);
    }

    // a{b{d,e{g,h{,I}}},c{f}}
    private static TreeNode buildTree(String input, int index) {
        if (index >= input.length() || input.charAt(index) == ',' || input.charAt(index) == '}') {
            return null;
        }
        TreeNode curNode = new TreeNode(input.charAt(index));
        // 跳过当前节点的字符
        index++;
        // 跳过空节点
        while (index < input.length() && input.charAt(index) == ',') {
            index++;
        }

        // 构建左子树
        if (index < input.length() && input.charAt(index) == '{') {
            curNode.left = buildTree(input, index + 1);
            // 找到左子树的结束
            index = findClosingBrace(input, index) + 1;
        }

        // 构建右子树
        if (index < input.length() && input.charAt(index) == ',') {
            index++; // 跳过逗号
            while (index < input.length() && input.charAt(index) == ',') {
                index++; // 跳过空节点
            }
            if (index < input.length() && input.charAt(index) == '{') {
                curNode.right = buildTree(input, index + 1);
                index = findClosingBrace(input, index) + 1;
            }
        }

        return curNode;
    }

    private static int findClosingBrace(String input, int openBraceIndex) {
        // 开始时有一个左大括号
        int balance = 1;
        for (int i = openBraceIndex + 1; i < input.length(); i++) {
            if (input.charAt(i) == '{') {
                balance++;
            } else if (input.charAt(i) == '}') {
                balance--;
                if (balance == 0) {
                    // 找到配对的右大括号
                    return i;
                }
            }
        }
        return -1;
    }

    private static int findChartIndex(String input, int start, int end, char c) {
        for (int i = start; i <= end; i++) {
            if (input.charAt(i) == c) {
                return i;
            }
        }
        return -1;
    }

}
